package com.atguigu.hadoop.examples.mapreduce.terasort;


import com.google.common.base.Charsets;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.mapreduce.InputSplit;
import org.apache.hadoop.mapreduce.lib.input.FileSplit;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

class TeraScheduler
{
    private static final Logger LOG = LoggerFactory.getLogger(TeraScheduler.class)
            ;
    private Split[] splits;
    private List<Host> hosts = new ArrayList();
    private int slotsPerHost;
    private int remainingSplits = 0;
    private FileSplit[] realSplits = null;

    List<String> readFile(String filename)
            throws IOException
    {
        List result = new ArrayList(10000);
        BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream(filename), Charsets.UTF_8)); Throwable localThrowable3 = null;
        try {
            String line = in.readLine();
            while (line != null) {
                result.add(line);
                line = in.readLine();
            }
        }
        catch (Throwable localThrowable1)
        {
            localThrowable3 = localThrowable1; throw localThrowable1;
        }
        finally
        {
            if (in != null) if (localThrowable3 != null) try { in.close(); } catch (Throwable localThrowable2) { localThrowable3.addSuppressed(localThrowable2); } else in.close();
        }
        return result;
    }

    public TeraScheduler(String splitFilename, String nodeFilename) throws IOException
    {
        this.slotsPerHost = 4;

        Map hostIds = new HashMap();
        for (Iterator localIterator = readFile(nodeFilename).iterator(); localIterator.hasNext(); ) {
            String hostName = (String)localIterator.next();
            Host host = new Host(hostName);
            this.hosts.add(host);
            hostIds.put(hostName, host);
        }
        String hostName;
        List<String> splitLines = readFile(splitFilename);
        this.splits = new Split[splitLines.size()];
        this.remainingSplits = 0;
        for (String line : splitLines) {
            StringTokenizer itr = new StringTokenizer(line);
            Split newSplit = new Split(itr.nextToken());
            this.splits[(this.remainingSplits++)] = newSplit;
            while (itr.hasMoreTokens()) {
                Host host = (Host)hostIds.get(itr.nextToken());
                newSplit.locations.add(host);
                host.splits.add(newSplit);
            }
        }
    }

    public TeraScheduler(FileSplit[] realSplits, Configuration conf) throws IOException
    {
        this.realSplits = realSplits;
        this.slotsPerHost = conf.getInt("mapreduce.tasktracker.map.tasks.maximum", 4);
        Map hostTable = new HashMap();
        this.splits = new Split[realSplits.length];
        for (FileSplit realSplit : realSplits) {
            Split split = new Split(realSplit.getPath().toString());
            this.splits[(this.remainingSplits++)] = split;
            for (String hostname : realSplit.getLocations()) {
                Host host = (Host)hostTable.get(hostname);
                if (host == null) {
                    host = new Host(hostname);
                    hostTable.put(hostname, host);
                    this.hosts.add(host);
                }
                host.splits.add(split);
                split.locations.add(host);
            }
        }
    }

    Host pickBestHost() {
        Host result = null;
        int splits = 2147483647;
        for (Host host : this.hosts) {
            if (host.splits.size() < splits) {
                result = host;
                splits = host.splits.size();
            }
        }
        if (result != null) {
            this.hosts.remove(result);
            LOG.debug("picking " + result);
        }
        return result;
    }

    void pickBestSplits(Host host) {
        int tasksToPick = Math.min(this.slotsPerHost,
                (int)Math.ceil(this.remainingSplits / this.hosts
                        .size()));
        Split[] best = new Split[tasksToPick];
        for (Iterator localIterator1 = host.splits.iterator(); localIterator1.hasNext(); ) {
            Split cur = (Split)localIterator1.next();
            LOG.debug("  examine: " + cur.filename + " " + cur.locations.size());
            int i = 0;
            while ((i < tasksToPick) && (best[i] != null) &&
                    (best[i].locations
                            .size() <= cur.locations.size())) {
                i++;
            }
            if (i < tasksToPick) {
                for (int j = tasksToPick - 1; j > i; j--) {
                    best[j] = best[(j - 1)];
                }
                best[i] = cur;
            }
        }

        for (int i = 0; i < tasksToPick; i++) {
            if (best[i] != null) {
                LOG.debug(" best: " + best[i].filename);
                for (Host other : best[i].locations) {
                    other.splits.remove(best[i]);
                }
                best[i].locations.clear();
                best[i].locations.add(host);
                best[i].isAssigned = true;
                this.remainingSplits -= 1;
            }
        }

        for (Split cur : host.splits)
            if (!cur.isAssigned)
                cur.locations.remove(host);
    }

    void solve()
            throws IOException
    {
        Host host = pickBestHost();
        while (host != null) {
            pickBestSplits(host);
            host = pickBestHost();
        }
    }

    public List<InputSplit> getNewFileSplits()
            throws IOException
    {
        solve();
        FileSplit[] result = new FileSplit[this.realSplits.length];
        int left = 0;
        int right = this.realSplits.length - 1;
        String[] newLocations;
        for (int i = 0; i < this.splits.length; i++) {
            if (this.splits[i].isAssigned)
            {
                newLocations = new String[] { ((Host)this.splits[i].locations.get(0)).hostname };
                this.realSplits[i] = new FileSplit(this.realSplits[i].getPath(), this.realSplits[i]
                        .getStart(), this.realSplits[i].getLength(), newLocations);
                result[(left++)] = this.realSplits[i];
            } else {
                result[(right--)] = this.realSplits[i];
            }
        }
        List ret = new ArrayList();
        for (FileSplit fs : result) {
            ret.add(fs);
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        TeraScheduler problem = new TeraScheduler("block-loc.txt", "nodes");
        for (Host host : problem.hosts) {
            System.out.println(host);
        }
        LOG.info("starting solve");
        problem.solve();
        List<Split> leftOvers = new ArrayList();
        for (int i = 0; i < problem.splits.length; i++) {
            if (problem.splits[i].isAssigned)
                System.out.println("sched: " + problem.splits[i]);
            else {
                ((List)leftOvers).add(problem.splits[i]);
            }
        }

        System.out.println("left over: " + ((List)leftOvers).size());
        LOG.info("done");
    }

    static class Host
    {
        String hostname;
        List<TeraScheduler.Split> splits = new ArrayList();

        Host(String hostname) { this.hostname = hostname; }

        public String toString() {
            StringBuffer result = new StringBuffer();
            result.append(this.splits.size());
            result.append(" ");
            result.append(this.hostname);
            return result.toString();
        }
    }

    static class Split
    {
        String filename;
        boolean isAssigned = false;
        List<TeraScheduler.Host> locations = new ArrayList();

        Split(String filename) { this.filename = filename; }

        public String toString() {
            StringBuffer result = new StringBuffer();
            result.append(this.filename);
            result.append(" on ");
            for (TeraScheduler.Host host : this.locations) {
                result.append(host.hostname);
                result.append(", ");
            }
            return result.toString();
        }
    }
}